package com.gitee.brtree.BlackRedTree;

/**
 * @author ming.yan-1
 * @version V1.0
 * @Title com.gitee.brtree.BlackRedTree
 * @Description
 * @date 2018/9/17  下午3:24
 */
public class BlackRedTree<T extends Comparable<T>> {


    private T data;
    private BlackRedTree<T> left;
    private BlackRedTree<T> right;
    private BlackRedTree<T> parent;

    /**
     * true red
     * false black
     */
    private boolean color;


    public BlackRedTree(T data, BlackRedTree<T> parent, BlackRedTree<T> left, BlackRedTree<T> right) {
        this.data = data;
        this.color = true;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    /***********************左旋**************/
    /**
     *
     * 左旋示意图：对节点x进行左旋
     *     p                       p
     *    /                       /
     *   x                       y
     *  / \                     / \
     * lx  y      ----->       x  ry
     *    / \                 / \
     *   ly ry               lx ly
     *
     */
    private void leftRotate(BlackRedTree<T> x) {

        BlackRedTree<T> y = x.right;

        //ly 可能是空
        BlackRedTree<T> ly = y.left;

        //p 可能是空
        BlackRedTree<T> p = x.parent;

        if(ly != null){
            ly.parent = x;
        }

        //如果ly是null，则x.right正好为null，没有子节点
        x.right = ly;

        y.left = x;

        x.parent = y;

        //如果x为root节点，则把root指向y即可，此处明白道理，就不写多余代码了
        y.parent = p;



        //如果x是root的前继节点，则y仍为前继，如果x是root的后继节点，则y仍为后继
        if(p.left == x){
            p.left = y;
        }else {
            p.right = y;
        }
    }

    /***********************左旋**************/
    /**
     * 左旋示意图：对节点y进行右旋
     *        p                   p
     *       /                   /
     *      y                   x
     *     / \                 / \
     *    x  ry   ----->      lx  y
     *   / \                     / \
     * lx  rx                   rx ry
     *
     */
    private void rightRotate(BlackRedTree<T> x){
        //与左旋同理
    }



    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BlackRedTree<T> getLeft() {
        return left;
    }

    public void setLeft(BlackRedTree<T> left) {
        this.left = left;
    }

    public BlackRedTree<T> getRight() {
        return right;
    }

    public void setRight(BlackRedTree<T> right) {
        this.right = right;
    }

    public BlackRedTree<T> getParent() {
        return parent;
    }

    public void setParent(BlackRedTree<T> parent) {
        this.parent = parent;
    }

    public boolean isColor() {
        return color;
    }

    public void setColor(boolean color) {
        this.color = color;
    }
}
